#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<iostream>
using namespace std;

typedef char TreeType;
struct TreeNode
{
	TreeNode* left;
	TreeNode* right;
	TreeType val;
	TreeNode(TreeType v = TreeType()) : left(nullptr),right(nullptr),val(v)
	{}
};

TreeNode* CopyTree(TreeNode* root)
{
	if (!root) return nullptr;
	TreeNode* newNode = new TreeNode(root->val);
	newNode->left = CopyTree(root->left);
	newNode->right = CopyTree(root->right);
	return newNode;
}

//前序遍历
void PreOrder(TreeNode* root)
{
	if (root == nullptr) return;
	cout << root->val << " ";
	PreOrder(root->left);
	PreOrder(root->right);
}
//中序遍历
void InOrder(TreeNode* root)
{
	if (root == nullptr) return;
	PreOrder(root->left);
	cout << root->val << " ";
	PreOrder(root->right);
}
//后序遍历
void PostOrder(TreeNode* root)
{
	if (root == nullptr) return;
	PreOrder(root->left);
	PreOrder(root->right);
	cout << root->val << " ";
}
//二叉树的销毁
void BinaryTreeDestory(TreeNode* root)
{
	if (root == nullptr) return;
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	delete root;
}
//二叉树叶子结点个数
int BinaryTreeLeafSize(TreeNode* root)
{
	if (root == nullptr) return 0;
	if (!root->left && !root->right) return 1;

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
//二叉树结点个数
int  BinaryTreeSize(TreeNode* root)
{
	if (!root) return 0;
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//求第K层结点个数
int BinaryTreeLevelSize(TreeNode* root, int k)
{
	if (!root) return 0;
	if (k == 1) return 1;
	return BinaryTreeLevelSize(root->left, k - 1) + BinaryTreeLevelSize(root->right, k - 1);
}
//二叉树的高度/深度
int BinaryTreeDepth(TreeNode* root)
{
	if (!root) return 0;
	return 1 + max(BinaryTreeDepth(root->left), BinaryTreeDepth(root->right));
}
//查找值为x的结点
TreeNode* BinaryTreeFind(TreeNode* root, TreeType x)
{
	if (!root) return nullptr;
	if (root->val == x) return root;

	TreeNode* leftAns = BinaryTreeFind(root->left, x);
	if (leftAns != nullptr)
		return leftAns;
	else
		return BinaryTreeFind(root->right, x);
}
